universal hash function

Definition

A random hash function $h: \mathcal{U} \rightarrow \{1,…,m\}$ is universal if, for any fixed $x,y \in \mathcal{U}$,

Efficient construction: Let $p$ be a prime number between $|\mathcal{U}|$ and $2|\mathcal{U}|$. Let $a$, $b$ be random numbers in $0,…,p$, $a \neq 0$.

is universal.

See also: Hashing
Compare: uniformly random hash function